/* 求解二叉树的宽度 */
#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 构建 记录每一层宽度的数组，h为当前所在层
void LevelWidth(BiTree T, int a[], int h)
{
  // 结点不为空
  if (T != NULL)
  {
    // 当前层的宽度+1
    a[h] += 1;
    
    // 进入左子树
    LevelWidth(T->lchild, a, h + 1);
    
    // 进入右子树
    LevelWidth(T->rchild, a, h + 1);
  }
}

// 求二叉树的宽度 -- 方法一
int width(BiTree T)
{
  // 数组，记录每一层的宽度
  int a[maxsize], h = 1;
  for (int i = 0; i <= maxsize; i++)
    a[i] = 0;
  
  // 填充数组
  LevelWidth(T, a, h);
  
  // 遍历数组
  int wid = a[0];
  for (int i = 1; i <= maxsize; i++)
    if (a[i] > wid)
      wid = a[i]; // 更新最大宽度
    
  // 返回二叉数组宽度
  return wid;
}

// 二叉树结点
typedef struct
{
  BTNode *p;
  int lno; // 结点层号
} St[maxsize];

// 求二叉树的宽度 -- 方法二
int width2(BTNode *boot)
{
  // 创建队列
  St que;
  int front = 0, rear = 0;
  
  int Lno, i = 1, max = 0;
  
  // 如果访问结点不为空
  if (boot != NULL)
  {
    // 结点进队列
    que[++rear].p = boot;
    
    // 更新长度
    que[rear].lno = 1;
    
    // 队列不为空
    while (front != rear)
    {
      // 结点出队
      BTNode *q = que[++front].p;
      
      // 记录结点层号
      Lno = que[front].lno;
      
      // 左孩子结点进队
      if (q->lchild != NULL)
      {
        que[++rear].p = q->lchild; // 进队
        que[rear].lno = Lno + 1; // 层号
      }
      
      // 右孩子结点进队
      if (q->rchild != NULL)
      {
        que[++rear].p = q->rchild; // 进队
        que[rear].lno = Lno + 1; // 层号
      }
    }
    
    // 遍历队列
    while (i <= rear)
    {
      int n = 0;
      int k = que[i].lno; // 记录层号
      
      // 遍历同一层的结点
      while (i <= rear && que[i].lno == k)
      {
        ++i;
        ++n; // 记录该层结点个数
      }
      
      // 记录最大宽度
      if (n > max)
        max = n;
    }
  }
  
  // 更新宽度
  return max;
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  cout << "二叉树的宽度为:" << width2(T) << endl;
}
